#include<bits/stdc++.h>
using namespace std;

struct Node{
    int element;
    Node *left = NULL, *right = NULL;
};

class BST{
private:
    Node *root;

    void BST_DELETE(Node *root);

public:
    BST() { root = NULL;}
    ~BST(); //todo

    Node* getRoot() { return root;}
    void insert(int element);
    void preList(Node *root);
    void midList(Node *root);
    void afterList(Node *root);
};

void BST::BST_DELETE(Node *root){
    if(root == NULL) return;
    BST_DELETE(root->left);
    BST_DELETE(root->right);
    delete root;
}

BST::~BST(){
    BST_DELETE(root);
}

void BST::insert(int element){
    if(root == NULL) {
        root = new Node;
        root->element = element;
        return;
    }
    Node *p = root, *fp = root;
    while(p != NULL){
        if(p->element > element) { fp = p; p = p->left;}
        else if(p->element < element) {fp = p; p = p->right;}
        else {  //重复元素不处理
            return; //终止插入
        }
    }
    Node *newNode = new Node;   newNode->element = element;
    if(fp->element > element) fp->left = newNode;
    else fp->right = newNode;
}

void BST::preList(Node *root){
    if(root == NULL) return;

    cout<<root->element<<' ';
    preList(root->left);
    preList(root->right);
}

void BST::midList(Node *root){
    if(root == NULL) return;

    midList(root->left);
    cout<<root->element<<' ';
    midList(root->right);
}

void BST::afterList(Node *root){
    if(root == NULL) return;

    afterList(root->left);
    afterList(root->right);
    cout<<root->element<<' ';
}

int main(){
    int n;
    while(cin>>n){
        BST bst;
        for(int i=0; i<n; ++i){
            int a;
            cin>>a;
            bst.insert(a);
        }

        bst.preList(bst.getRoot()); cout<<endl;
        bst.midList(bst.getRoot()); cout<<endl;
        bst.afterList(bst.getRoot()); cout<<endl;
    }
    return 0;
}